package leetcode.code015;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution extends Solution015 {

	@Override
	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> result = new ArrayList<>();
		if (nums == null || nums.length < 3)
			return result;
		Arrays.sort(nums);
		int len = nums.length;
		int p = 0;
		while (p < len) {
			int num = nums[p];
			List<List<Integer>> temp = twoSum(nums, p + 1, len - 1, num);
			if (temp.size() != 0)
				result.addAll(temp);
			while (p < len && nums[p] == num) {
				p++;
			}
		}
		return result;
	}

	private List<List<Integer>> twoSum(int[] nums, int l, int r, int num) {
		List<List<Integer>> result = new ArrayList<>();
		while (l < r) {
			int numl = nums[l];
			int numr = nums[r];
			if (numl + numr + num == 0) {
				List<Integer> temp = new ArrayList<>();
				temp.add(num);
				temp.add(numl);
				temp.add(numr);
				result.add(temp);
				while (l < r && nums[l] == numl) {
					l++;
				}
				while (l < r && nums[r] == numr) {
					r--;
				}
			} else if (numl + numr + num > 0) {
				while (l < r && nums[r] == numr) {
					r--;
				}
			} else {
				while (l < r && nums[l] == numl) {
					l++;
				}
			}
		}
		return result;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug1();
//		so.debug2();
//		so.debug3();
		so.debug4();

		int[] array = new int[] { 0, 1, 2, 3, 3, 3, 3, 3, 4 };
		int p = 0;
		while (p < array.length) {
			int now = array[p];
			System.out.println("p>>  " + p + "now>>   " + now);
			while (p < array.length && array[++p] == now) {
				// p++;
				// System.out.println("p>>>>" + p + "now>>>>" + now);
			}
		}

	}

}
